#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

class Solution
{
public:
    vector<int> topKFrequent(vector<int> nums, int k)
    {
        // 哈希表记录每个元素出现的次数
        unordered_map<int, int> countMap;
        for (int num : nums)
        {
            countMap[num]++;
        }

        // 使用优先队列维护出现次数最多的元素
        priority_queue<pair<int, int>> pq;
        for (auto it : countMap)
        {
            // counts,num
            // 优先队列中存储的是pair<int, int>类型的元素，其中第一个元素是counts，第二个元素是num
            pq.push(make_pair(it.second, it.first));
            //cout<<pq.top().first<<" "<<pq.top().second<<endl;   
            // if (pq.size() > k)
            // {
            //     pq.pop();
            // }
        }
        // 
        // 构建结果数组
        vector<int> result(k);
        // 遍历优先队列，取出出现次数最多的k个元素
        cout<<"优先队列：\n";
        while (!pq.empty())
        {
            cout<<pq.top().first<<" "<<pq.top().second<<endl;
            result[k - 1] = pq.top().second;
            pq.pop();
           k--;
        }
        return result; 
    }
};

int main()
{
    Solution s;
    vector<int> result;
    //result = s.topKFrequent(vector<int>{1, 1, 1, 2, 2, 3}, 2);
     result = s.topKFrequent(vector<int>{1,1,1,2,2,3}, 2);
    for (int i = 0; i < result.size(); i++)
    {
        cout << result[i] << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}
